package com.wzq.solution;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.List;

class Solution377 {
   static int rst=0;

    /**********超时了******/
    /*public int combinationSum4(int[] nums, int target) {
        
        Arrays.sort(nums);
        foo(nums,target,0);
        return rst;
    }
    
    
    public void foo(int[] nums, int target,int sum) {
        if(sum == target){
            rst++;
        }else{
            for(int i=0;i<nums.length;i++){
                if(sum + nums[i] <= target){
                    foo(nums,target,sum+ nums[i]);
                }
                
            }
        }
    }
    */


    public static int combinationSum4(int[] nums, int target){
        Arrays.sort(nums);
        foo(nums,target,new ArrayList<Integer>(),nums.length-1,0);
        return rst;
    }


    public static void foo(int[] nums, int y,List<Integer> cntList,int k,int numCnt) {
        if(y == 0){
            //阶乘
            System.out.println(cntList);
            if(cntList.size() == 1){
                rst++;
            }else{
                int tmpCnt=1;
                for (int i=1,j=1,m=0;j<=numCnt;j++){
                    tmpCnt = tmpCnt*j/i;
                    if(i == cntList.get(m)) {
                        i = 1;
                        m++;
                    }else{
                        i++;
                    }
                }
                rst += tmpCnt;
            }

        }else{
            for(int i=k;i>=0;i--){
                if(nums[i]<=y){

                    int s = y/nums[i];
                    int j=s;
                    //for (int j=s;j>0;j--){
                        List<Integer> newList = new ArrayList<Integer>(cntList);
                        newList.add(j);
                        foo(nums,y%nums[i]+nums[i]*(s-j),newList,i-1,numCnt+j);
                    //}

                }
            }
        }
    }

    public static void main(String[] args) {
        long t1=System.currentTimeMillis();
        System.out.println(combinationSum4(new int[]{10,20,30,40,50,60,70,80,90,100,110,120,130,140,150,160,170,180,190,200,210,220,230,240,250,260,270,280,290,300,310,320,330,340,350,360,370,380,390,400,410,420,430,440,450,460,470,480,490,500,510,520,530,540,550,560,570,580,590,600,610,620,630,640,650,660,670,680,690,700,710,720,730,740,750,760,770,780,790,800,810,820,830,840,850,860,870,880,890,900,910,920,930,940,950,960,970,980,990,111},999));
        System.out.println(System.currentTimeMillis()-t1);

    }
}